package array;

public class leetCode215_findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0) return -1;
        return getKth(nums,k - 1,0,nums.length - 1);
    }

    public int getKth(int[] nums,int k,int start,int end){
        if(start >= end){
            return nums[end];
        }
        int partition = partition(nums,start,end);
        if(partition < k){
            return partition(nums,partition + 1,end);
        }else if(partition > k){
            return partition(nums,start,partition - 1);
        }else{
            return nums[partition];
        }

    }

    public int partition(int[] nums,int start,int end){
        int base = nums[start];
        int i = start;
        int j = end;
        while (i < j){
            while (i < j &&  nums[j] < base){
                j--;
            }
            while (i < j && nums[i] >= base){
                i++;
            }
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        int tmp = nums[i];
        nums[i] = nums[start];
        nums[start] = tmp;

        return i;
    }

}
